import java.util.Arrays;

/*
算法构思：

贪心

动态规划和贪心的区别，在于是否直接在原数组上进行计算。动态规划会将索引位 i 的子数组最大和，重新放入 num[i]，替换原值

核心思路：

设以索引位 i-1 结尾的的数组前面部分的子数组最大和为 sumMax[i-1]

要计算以索位 i 结尾的子数组最大和:
如果 sumMax[i-1] >= 0 ,则 sumMax[i]=nums[i]+sumMax[i-1]
如果 sumMax[i-1] < 0 ,则 sumMax[i]=nums[i]

步骤：
1. 定义新数组，sumMax[]，按照核心思路，算出以索位 i 结尾的子数组最大和，全部存进去
2. 获取 sumMax[]中的最大值输出

*/
public class Solution_2 {
    public int maxSubArray(int[] nums) {
        //存储最大和的变量
        int [] sumMax=new int[nums.length];

        //初始化
        sumMax[0]=nums[0];
        int max= sumMax[0];
        //计算最大子数组和的数组
        for(int i=1;i<nums.length;i++)
        {
            if(sumMax[i-1]>=0)
            {
                sumMax[i]=nums[i]+sumMax[i-1];
            }
            else {
                sumMax[i]=nums[i];
            }
            max=Math.max(max,sumMax[i]);
        }
        //返回数组最大值
        return max;
    }
}
